package algorithm.find;

import java.util.LinkedHashMap;

/**
 * @author: Oliver
 * @time: 2020/6/1/20:57
 * 二分查找法
 * 保证程序的正确性：循环不变量设置，改变变量的值，但是不能改变变量的具体定义。
 */
public class BinarySearch {
    public static int binarySearch(int[] arr, int v) {
        return binarySearch2(arr, 0, arr.length - 1, v);

    }

    //    实现在[l,r]前鼻后鼻区间中查找元素
    private static int binarySearch(int[] arr, int l, int r, int v) {
        while (l <= r) {
            int mid = l + (r - l) >> 1;
            if (arr[mid] == v) {
                return mid;
            } else if (v > arr[mid]) {//比中间元素大，l=mid+1
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
//        int[] arr = {12, 34, 45, 56, 67, 78, 89, 90, 123};
//        int i = binarySearch(arr, 67);
        LinkedHashMap<String, String> hashMap = new LinkedHashMap<>();
        hashMap.put("123123", "qweqw");
        hashMap.put("1231231", "qweqw");
        System.out.println(hashMap);
    }

    //使用递归实现二分查找
    private static int binarySearch2(int[] arr, int l, int r, int v) {
        if (l >= r) {
            return -1;
        }

//        计算中间值
        int mid = l + (r - l) >> 1;

        if (arr[mid] == v) {
            return mid;
        } else if (v > arr[mid]) {
            l = mid + 1;
            return binarySearch2(arr, l, r, v);
        } else {
            r = mid - 1;
            return binarySearch2(arr, l, r, v);
        }
    }
}
